#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

/*
421. 数组中两个数的最大异或值
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
 

提示：

1 <= nums.length <= 2 * 105
0 <= nums[i] <= 231 - 1
*/

// 法一
class TrieNode {
    public:
    TrieNode* child[2]; // 0 和 1
    TrieNode() : child{nullptr, nullptr} {}
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        int maxXor = 0;

        // 插入
        auto insert = [&](int num) {
            TrieNode* cur = root;
            for(int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if(cur->child[bit] == nullptr)  cur->child[bit] = new TrieNode();
                cur = cur->child[bit];
            }
        };

        // 查找最大异或值
        auto findMaxXor = [&](int num) -> int {
            TrieNode* cur = root;
            int xorVal = 0;
            for(int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                int opposite = 1 - bit;
                
                if(cur->child[opposite] != nullptr) { // 有相反的位可以异或
                    xorVal = (xorVal << 1) | 1;
                    cur = cur->child[opposite];
                } else { // 没有相反的位，继续走当前路径
                    xorVal = (xorVal << 1) | 0;
                    cur = cur->child[bit];  // 这里使用bit而不是opposite
                }
            }
            return xorVal;
        };

        // 遍历计算每个数字都插入Trie来计算
        for(int num : nums) insert(num);
        for(int num : nums) maxXor = max(maxXor, findMaxXor(num));

        return maxXor;
    }
};    
    

// 法二
class Solution2 {
    public:
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        int high = 0;
        int maxNum = 0;
        for (int num : nums) {
            maxNum = max(num, maxNum);
        }
        for (int i = 0; i < 32; i++) {
            if ((maxNum >> i) == 0) {
                break;
            }
            high++;
        }
        // 哈希来换时间
        unordered_set<int> seen;
        for (int i = high; i >= 0; i--) {
            int better = ans | (1 << i);
            seen.clear();
            for (int num : nums) {
                num = (num >> i) << i;
                seen.insert(num);
                if (seen.find(better ^ num) != seen.end()) {
                    ans = better;
                    break;
                }
            }
        }
        return ans;
    }
};